\section{Algorithm for $k$ Random Walks}\label{sec:k-algo}
The previous section was devoted to performing a single random walk of length $\tau$ (mixing time) efficiently to sample from the stationary distribution. In many applications, one typically requires a large number of random walk samples. A larger amount of samples allows for a better estimation of the problem at hand. In this section we focus on obtaining several random walk samples.  Specifically, we consider the scenario when we want to compute $k$ independent walks each of
length $\tau$ from different (not necessarily distinct) sources $s_1, s_2, \ldots, s_k$. We show that {\sc Single-Random-Walk} (cf. Algorithm~\ref{alg:single-random-walk} in Appendix) can be extended to solve this problem. In particular, the algorithm {\sc Many-Random-Walks} (cf. Algorithm~\ref{alg:many-random-walk} in Appendix) to compute $k$ walks is essentially repeating the {\sc Single-Random-Walk} algorithm on each source with one common/shared phase, and yet through overlapping computation, completes faster than $k$ times the previous bound. The crucial observation is that we have to do Phase 1 only once and still ensure all walks are independent. The pseudo code of the algorithm, analysis and proof of the main result can be found in Section \ref{multiple walks} in the Appendix.

\iffalse
\vspace{-0.06in}
\paragraph{{\sc Many-Random-Walks} :} Let $\lambda=(32 \sqrt{k\tau \Phi+1}\log n+k)(\log n)^2$. If
$\lambda \ge \tau$ then run the naive random walk algorithm. %, i.e., the sources find walks of length $\tau$ simultaneously by sending tokens. 
Otherwise, do the following. First, modify Phase~2 of {\sc Single-Random-Walk} to create multiple walks, one at a time; i.e., in the second phase, we stitch the short walks together to get a
walk of length $\tau$ starting at $s_1$ then do the same thing for $s_2$, $s_3$, and so on. We show that {\sc Many-Random-Walks} algorithm finishes in $\tilde O\left(\min(\sqrt{k\tau \Phi}, k+\tau)\right)$ rounds with high probability. This result is also stated in the Theorem \ref{thm:kwalks} (Section \ref{sec:results}). Since the details of this specific extension is similar to the previous ideas even for the dynamic setting, the formal proofs are placed in the Appendix (Section \ref{multiple walks}).

\fi
%\begin{theorem}\label{thm:kwalks} {\sc Many-Random-Walks} finishes in
%$\tilde O\left(\min(\sqrt{k\tau \Phi}, k+\tau)\right)$
%rounds with high probability.
%\end{theorem}
%\begin{proof}
%See Section \ref{multiple walks} in Appendix.
%\end{proof}
